use std::{cell::RefCell, fmt, rc::Rc};

#[derive(Clone)]
pub struct AdjacencyListNode {
    v: u32,
    list: Vec<(u32, u32)>,
}

impl fmt::Display for AdjacencyListNode {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        print!("{} -> ", self.v);
        for node in self.list.iter() {
            print!("{}_{} -> ", node.0, node.1);
        }
        print!("Null\n");
        write!(f, "")
    }
}

impl AdjacencyListNode {
    pub fn build(v: u32, list: Vec<(u32, u32)>) -> Self {
        AdjacencyListNode { v, list }
    }
    pub fn get_v(&self) -> u32 {
        self.v
    }
    pub fn get_list(&self) -> Vec<(u32, u32)> {
        self.list.clone()
    }
    pub fn list_push(&mut self, v: (u32, u32)) {
        self.list.push(v);
    }
    pub fn list_contains_v(&self, v: (u32, u32)) -> bool {
        self.list.contains(&v)
    }
    pub fn list_remove(&mut self, v: (u32, u32)) {
        let len = self.list.len();
        for i in 0..len {
            if self.list[i] == v {
                self.list.remove(i);
                break;
            }
        }
    }
}

#[derive(Clone)]
pub struct AdjacencyList {
    list: Vec<AdjacencyListNode>,
}

impl fmt::Display for AdjacencyList {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for node in self.list.iter() {
            println!("{}", node);
        }
        write!(f, "")
    }
}

impl AdjacencyList {
    pub fn build(list: Vec<AdjacencyListNode>) -> Self {
        AdjacencyList { list }
    }
    pub fn find(&self, v: u32) -> Vec<(u32, u32)> {
        let mut res = vec![];
        for node in self.list.iter() {
            if node.get_v() == v {
                res = node.get_list().clone();
                break;
            }
        }
        res
    }
    pub fn node_push(&mut self, node: u32, v: (u32, u32)) {
        for node_v in self.list.iter_mut() {
            if node_v.get_v() == node {
                node_v.list_push(v);
                break;
            }
        }
    }
    pub fn get_list(&self) -> Vec<AdjacencyListNode> {
        self.list.clone()
    }
}

#[derive(Clone, Copy, PartialEq)]
pub enum MapNodeColor {
    WHITE,
    GRAY,
    BLACK,
}
impl fmt::Display for MapNodeColor {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match *self {
            MapNodeColor::WHITE => write!(f, "white"),
            MapNodeColor::GRAY => write!(f, "gray"),
            MapNodeColor::BLACK => write!(f, "black"),
        }
    }
}

pub struct MapNode {
    v: u32,
    color: RefCell<MapNodeColor>,
    p: RefCell<Option<u32>>,
    d: RefCell<u32>,
    l: RefCell<u32>,
}

impl fmt::Display for MapNode {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}  {}  {} ~ {}",
            self.v,
            self.get_color(),
            self.get_d(),
            self.get_l()
        )
    }
}
impl MapNode {
    pub fn build(v: u32) -> Self {
        MapNode {
            v,
            color: RefCell::new(MapNodeColor::WHITE),
            p: RefCell::new(None),
            d: RefCell::new(0),
            l: RefCell::new(0),
        }
    }
    pub fn get_v(&self) -> u32 {
        self.v
    }
    pub fn get_color(&self) -> MapNodeColor {
        unsafe { *(self.color.as_ptr()) }
    }
    pub fn get_d(&self) -> u32 {
        unsafe { *(self.d.as_ptr()) }
    }
    pub fn get_l(&self) -> u32 {
        unsafe { *(self.l.as_ptr()) }
    }
    pub fn get_p(&self) -> Option<u32> {
        unsafe {
            if let Some(l) = (*(self.p.as_ptr())).as_ref() {
                Some(*l)
            } else {
                None
            }
        }
    }
    pub fn set_color(&self, c: MapNodeColor) {
        *(self.color.borrow_mut()) = c;
    }
    pub fn set_d(&self, d: u32) {
        *(self.d.borrow_mut()) = d;
    }
    pub fn d_inc(&self) {
        *(self.d.borrow_mut()) += 1;
    }
    pub fn set_p(&self, p: u32) {
        *(self.p.borrow_mut()) = Some(p);
    }
    pub fn set_l(&self, l: u32) {
        *(self.l.borrow_mut()) = l;
    }
}

pub struct Map {
    list: Vec<Rc<MapNode>>,
    ajc_list: AdjacencyList,
}

impl fmt::Display for Map {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for node in self.list.iter() {
            write!(f, "{}\n", node).unwrap();
        }
        write!(f, "Over!\n")
    }
}

impl Map {
    pub fn build(ajc_list: AdjacencyList) -> Self {
        let mut list: Vec<Rc<MapNode>> = vec![];
        for node in ajc_list.get_list() {
            list.push(Rc::new(MapNode::build(node.get_v())));
        }
        Map { list, ajc_list }
    }
    pub fn find(&self, v: u32) -> Rc<MapNode> {
        let mut n = Rc::new(MapNode::build(0));
        for node in self.list.iter() {
            if node.get_v() == v {
                n = Rc::clone(node);
                break;
            }
        }
        n
    }
    pub fn bfs(&self, s: u32) {
        self.find(s).set_color(MapNodeColor::GRAY);
        let mut q: Vec<u32> = vec![];
        q.push(s);
        let mut u;
        while !(q.is_empty()) {
            u = q[0];
            q.remove(0);
            for node in self.ajc_list.find(u) {
                let map_node = self.find(node.0);
                if map_node.get_color() == MapNodeColor::WHITE {
                    map_node.set_color(MapNodeColor::GRAY);
                    map_node.set_d(self.find(u).get_d() + 1);
                    map_node.set_p(u);
                    q.push(node.0);
                }
            }
            self.find(u).set_color(MapNodeColor::BLACK);
        }
    }
    pub fn dfs(&self) {
        let mut time = 0;
        for node in self.list.iter() {
            if node.get_color() == MapNodeColor::WHITE {
                self.dfs_visit(node.get_v(), &mut time)
            }
            print!("Null\n")
        }
        print!("Null\n");
        println!("After dfs: ");
        println!("{}", self);
    }
    fn dfs_visit(&self, u: u32, time: &mut u32) {
        print!("{} -> ", u);
        *time += 1;
        let map_node_u = self.find(u);
        map_node_u.set_d((*time).clone());
        map_node_u.set_color(MapNodeColor::GRAY);
        for node in self.ajc_list.find(u) {
            let map_node_v = self.find(node.0);
            if map_node_v.get_color() == MapNodeColor::WHITE {
                map_node_v.set_p(u);
                self.dfs_visit(node.0, time);
            }
        }
        map_node_u.set_color(MapNodeColor::BLACK);
        *time += 1;
        map_node_u.set_l((*time).clone());
    }
    pub fn topological_sort(&self) -> Vec<u32> {
        let mut res = vec![];
        self.dfs();
        for node in self.list.iter() {
            if res.is_empty() {
                res.push(node.get_v());
            } else {
                res.push(node.get_v());
                for i in 0..res.len() {
                    if node.get_l() > self.find(res[i]).get_l() {
                        res.insert(i, node.get_v());
                        res.pop();
                        break;
                    }
                }
            }
        }
        println!("After topological: ");
        println!("{:?}", res);
        res
    }
    pub fn strongly_connected_components(&self) -> Vec<Vec<u32>> {
        let mut res: Vec<Vec<u32>> = vec![];
        println!("-------- Strongly Start ----------");
        let order_decrease = self.topological_sort();
        let mut ajc_list: Vec<AdjacencyListNode> = vec![];
        for v in order_decrease.iter() {
            ajc_list.push(AdjacencyListNode::build(*v, vec![]));
        }
        let mut ajc = AdjacencyList::build(ajc_list);
        for node in self.ajc_list.list.iter() {
            let node_v = node.get_v();
            for v in node.get_list().iter() {
                ajc.node_push((*v).0, (node_v, (*v).1));
            }
        }
        println!("转置邻接表生成完毕！");
        println!("{}", ajc);
        let map = Map::build(ajc);
        let order = map.topological_sort();
        let mut res_temp = vec![];
        let mut order_d_l: Vec<(u32, u32)> = vec![];
        let mut map_node;
        for v in order.iter() {
            map_node = map.find(*v);
            order_d_l.push((map_node.get_d(), map_node.get_l()));
        }
        println! {"order_d_l:\n{:?}", order_d_l};
        res_temp.push(order[0]);
        for id in 1..order.len() {
            if (order_d_l[id].0 < order_d_l[id - 1].0) || (order_d_l[id].1 > order_d_l[id - 1].1) {
                res.push(res_temp.clone());
                res_temp.clear();
            }
            res_temp.push(order[id]);
        }
        res.push(res_temp);
        println!("res:\n{:?}", res);
        res
    }
}
/*
   let mut a = vec![];
   a.push(AdjacencyListNode::build(1, vec![2, 4]));
   a.push(AdjacencyListNode::build(2, vec![5]));
   a.push(AdjacencyListNode::build(3, vec![6, 5]));
   a.push(AdjacencyListNode::build(4, vec![2]));
   a.push(AdjacencyListNode::build(5, vec![4]));
   a.push(AdjacencyListNode::build(6, vec![6]));
   let b = AdjacencyList::build(a);
   println!("{}", b);
   let map = Map::build(b);
   println!("{}", map);
   map.bfs(2);
   println!("{}", map);
*/

/*
  let mut a = vec![];
  a.push(AdjacencyListNode::build(1, vec![2, 5]));
  a.push(AdjacencyListNode::build(2, vec![3, 4]));
  a.push(AdjacencyListNode::build(3, vec![2]));
  a.push(AdjacencyListNode::build(4, vec![4]));
  a.push(AdjacencyListNode::build(5, vec![1, 4]));
  a.push(AdjacencyListNode::build(6, vec![1, 3, 7]));
  a.push(AdjacencyListNode::build(7, vec![3, 8]));
  a.push(AdjacencyListNode::build(8, vec![6]));
  let b = AdjacencyList::build(a);
  println!("{}", b);
  let map = Map::build(b);
  println!("{}", map);
  println!("{:?}", map.strongly_connected_components());
  println!("{}", map);
*/
